# this was downloaded from the internet. Source: http://code.google.com/p/techproj/source/browse/trunk/IntroAI/hw2/anytime_alpha_beta.py

import time
from timer import Timer, TimeoutException

# A bloody large number.
INFINITY = float('Inf')


class AlphaBetaAnytimeSearch:
	
	def __init__(self, player, time_limit, utility, w = 1, nro=None, quie=None,
				 max_depth=INFINITY):
		'''
		Constructor.
		
		@param player: Your player. This search algorithm will choose the best
					   actions for this player.
		@param time_limit: The maximum time limit to run.
		@param utility: An evaluation function for states.
		@param nro: Optional evaluation function for states that sets the order
					in which the nodes are searched (default: None).
		@param quie: Optional boolean function that given a state returns
					 whether or not to continue searching through it even though
					 we go beyond the maximum depth (default: None).
		@param max_depth: Optional maximum depth of the search tree.
		'''
		self.player = player
		self.time_limit = time_limit
		self.max_depth = max_depth

		self.utility = utility
		self.w = w;
		self.nro = nro
		self.quie = quie or (lambda state, over_depth: True)

	def search(self, current_state):
		'''
		Search game to determine best action; use timed alpha-beta pruning.
		Does an iterative deepening timed search, which returns the best
		possible action within the given time limit.
		
		@param current_state: The current game state to start the search from.
		'''
		# Initialize the timer that we will use to time our operation.
		self.timer = Timer(self.time_limit)

		# Simple protection from weird cases.
		successors = current_state.getSuccessors()
		if not successors:
			return None

		# The default action is simply the first, in case we have nothing smart
		# to say about it or we don't reach a conclusion within the time limit.
		best_value = -INFINITY
		best_action = successors.keys()[0]

		# Start iterating over depths until we run out of time, reach a
		# conclusive win or loss, or reach the maximum depth.
		max_depth = min(self.max_depth, current_state.getTurnsLeft())
		depth = 1
		while depth <= max_depth:
			#print "<<<%f>>> Starting search at depth: %d (best value so far: %f)" % (
				#time.clock() - self.timer.start, depth, best_value)

			# Perform a time check just before we do another search.
			if not self.timer.isTimeLeft():
				#print "<<<%f>>> No time for depth: %d" % (
				#	time.clock() - self.timer.start, depth)
				break

			# Perform the search up to the current depth.
			(current_action, current_value) = \
				self._searchUpToDepth(current_state, depth)

			# If the search didn't timeout, it has a better action.
			if current_action:
				best_value = current_value
				best_action = current_action
			else:
				#print "<<<%f>>> Search timed out at depth: %d" % (
					#time.clock() - self.timer.start, depth)
				break

			# If we have a conclusive win or loss, no point in continuing.
			if best_value == INFINITY or best_value == -INFINITY:
				#print "<<<%f>>> Search reached definite %s at depth: %d" % (
					#time.clock() - self.timer.start,
					#best_value == INFINITY and "WIN" or "LOSS",
					#depth)
				break
			
			depth += 1

		#print "<<<%f>>> Finished search (best value: %f)" % (
			#time.clock() - self.timer.start, best_value)
		return best_action
	
	def _searchUpToDepth(self, current_state, depth):
		'''
		Searches using alpha-beta pruning up to the given depth.
		'''
		best_value = -INFINITY
		best_action = None
		
		successors = current_state.getSuccessors().items()
		if self.nro:
			successors.sort(key=lambda (action, state): self.nro(state, self.player), reverse=True)
		if self.w != 1:
			successors = successors[0:int(len(successors)*self.w + 0.5)]


		for (action, state) in successors:
			value_fn = self._getValueFn(state)
			
			try:
				value = value_fn(state, best_value, INFINITY, 1, depth)
			except TimeoutException:
				return (None, -INFINITY)

			if value > best_value:
				best_value = value
				best_action = action

			if best_value == INFINITY:
				break
		
		return (best_action, best_value)
	
	def _getValueFn(self, state):
		if state.getCurrentPlayer() == self.player:
			return self._maxValue
		else:
			return self._minValue
	
	def _cutoffTest(self, state, depth, max_depth):
		'''
		Determines whether or not we should continue searching the successors
		of the given state, or stop and evaluate here.
		Performs the following checks:
		- If this state has a winner, return True to perform a cutoff.
		- Else, and if we are below the maximum depth, return False to continue.
		- Else, and if we the quiescence function returns True, do a cutoff.
		- Else, continue searching.
		'''
		if depth < max_depth:
			# If we are below the maximum depth, and there is a winner, cutoff.
			return state.getWinner() is not None

		# If we are at the maximum depth or above, and we have a winner or we
		# are at peace (quiescence returned True), cutoff.
		# If no winner and we are not yet at peace, continue.
		return ((state.getWinner() is not None) or
				self.quie(state, depth - max_depth))
	
	def _maxValue(self, state, alpha, beta, depth, max_depth):
		self.timer.check()

		if self._cutoffTest(state, depth, max_depth):
			return self.utility(state)
		
		successors = state.getSuccessors().values()
		if self.nro:
			successors.sort(key=lambda state: self.nro(state, self.player), reverse=True)
		if self.w != 1:
			successors = successors[0:int(len(successors)*self.w + 0.5)]

			
			
		value = -INFINITY
		for successor in successors:
			value_fn = self._getValueFn(successor)
			value = max(value, value_fn(
				successor, alpha, beta, depth + 1, max_depth))
			if value == INFINITY:
				return value
			if value >= beta:
				return value
			alpha = max(alpha, value)
		
		return value
	
	def _minValue(self, state, alpha, beta, depth, max_depth):
		self.timer.check()

		if self._cutoffTest(state, depth, max_depth):
			return self.utility(state)
		
		successors = state.getSuccessors().values()
		if self.nro:
			successors.sort(key=lambda state: self.nro(state, self.player))
		if self.w != 1:
			successors = successors[0:int(len(successors)*self.w + 0.5)]


		value = INFINITY
		for successor in successors:
			value_fn = self._getValueFn(successor)
			value = min(value, value_fn(
				successor, alpha, beta, depth + 1, max_depth))
			if value == -INFINITY:
				return value
			if value <= alpha:
				return value
			beta = min(beta, value)
		
		return value